package com.liner;

import java.sql.Array;
import java.util.Arrays;

/**
 * @author 一条淡水鱼 ゆ
 * @Classname MergeSort
 * @Description 归并排序
 * @Date 2023-04-01
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] array = BubbleSort.getInts();
        System.out.println(Arrays.toString(array));
        int[] newArray = mergeSort(array, 0, array.length - 1);

        System.out.println(Arrays.toString(newArray));
    }

    /**
     * @param array 原数组
     * @param start 需要被拆分的区间起始元素下标
     * @param end   需要被拆分的区间结束元素下标
     */
    private static int[] mergeSort(int[] array, int start, int end) {
        if (end == start) {
            return new int[]{array[start]};
        }

        int mid = start + (end - start) / 2;
        int[] leftArray = mergeSort(array, start, mid);
        int[] rightArray = mergeSort(array, mid + 1, end);


        //创建新的数组，存放合并后有序数组
        int[] newArray = new int[leftArray.length + rightArray.length];

        //声明变量  l、r、n  分别表示  leftArray、rightArray、newArray的数组下标
        int l = 0, n = 0, r = 0;
        //当 leftArray 和 rightArray 都没遍历结束之前

        while (l < leftArray.length && r < rightArray.length) {

            newArray[n++] = leftArray[l] <= rightArray[r] ? leftArray[l++] : rightArray[r++];
        }


        while (l < leftArray.length) {
            newArray[n++] = leftArray[l++];
        }

        while (r < rightArray.length) {
            newArray[n++] = rightArray[r++];
        }


        return newArray;
    }


}
